package huisu;

//矩阵中的路径
//用来判断一个矩阵中是否存在一条包含某字符串的路径，路径可以从任意一格开始，每一步可以在矩阵中向左右上下移动
//类似题目，在迷宫中找出口
public class RouteOfMatrix {

	public static int pathLength = 0;

	/**
	 * @param matrix
	 *            给定的矩阵
	 * @param str
	 *            要寻找的字符串
	 * @return 是否含有该字符串
	 */
	public static boolean hasPath(char[][] matrix, char[] str) {
		if (matrix == null || str == null || matrix.length <= 0) {
			return false;
		}
		int row = matrix.length, column = matrix[0].length; // 矩阵的行和列
		boolean[][] isVisited = new boolean[row][column]; // 用来标识是否已经访问
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < column; j++) {
				if (hasPathCore(matrix, row, column, i, j, str,
						isVisited)) {
					return true;
				}
			}
		}
		return false;
	}

	// 寻找字符序列的核心
	public static boolean hasPathCore(char[][] matrix, int row, int column, int i,
			int j, char[] str, boolean[][] isVisited) {
		//如果已经找到所有的字符，返回true
		if (pathLength == str.length) {
			return true;
		}
		boolean hasPath = false;
		if (i >= 0 && i < row && j >= 0 && j < column
				&& matrix[i][j] == str[pathLength] && !isVisited[i][j]) {
			++pathLength;
			isVisited[i][j] = true;
			hasPath = hasPathCore(matrix, row, column, i, j - 1, str, isVisited) // 上
					|| hasPathCore(matrix, row, column, i - 1, j, str, isVisited) // 左
					|| hasPathCore(matrix, row, column, i, j + 1, str, isVisited) // 下
					|| hasPathCore(matrix, row, column, i + 1, j, str, isVisited); // 右
			// 如果遍历上下左右的时候没有找到，那么将该节点删除，然后置已访问为false
			if (!hasPath) {
				--pathLength;
				isVisited[i][j] = false;
			}
		}
		return hasPath;
	}

	public static void main(String[] args) {
		char[] matrix = "ABCESFCSADEE".toCharArray();
		char[][] erMatrix = new char[3][4];
		int k = 0;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 4; j++) {
				erMatrix[i][j] = matrix[k++];
				System.out.print(erMatrix[i][j]);
			}
			System.out.println();
		}
		hasPath(erMatrix, "ABCCED".toCharArray());
	}
}
